 /*
 =====================================================================================
 *       Filename:  heap.cpp
 *
 *    Description:  A O(logn) method to find median of dynamic array.
 *
 *        Version:  1.0
 *        Created:  2012/2/22 18:10:32
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Zhigang Wang, 
 *   Organization:  test of Youdao
 *
 * =====================================================================================
*/
#include<iostream>
#include<algorithm>

#define N 1000
 // to do: use a dynamic array is better
 
using namespace std;

bool cmp(int a, int b);
void show_array(int *array, int n);
void init(int *small, int *big, int &n,int &middle, int &left, int &right);
void insert(int *small, int *big, int &n, int &middle, int &left, int &right);

bool cmp(int a, int b){
//compare function for small root heap
  return a > b;
}
int f():

void show_array(int *array, int n){
//show the numbers of array for testing
  int i;
  for(i = 0; i < n; i++)
	  cout<<*(array + i)<<' ';
  cout<<endl;
}

void init(int *small, int *big, int &n,int &middle, int &left, int &right){
//init the array of unsorted numbers
  int i,j;
  int m;
  cout<<"input tht numbers to init(-1 to end input):"<<endl;
  n = 0;
  make_heap(small, small + n);
  while ( 1 ) {
    cin>>small[n++];
    if( small[n - 1] == -1){
        n--;
        break;
    }
  }
  sort_heap(small, small + n);
  show_array(small, n);
  m = n / 2;
  middle = small[m];
  left = m;
  right = n - m -1;
  for (i=0, j = m + 1; j < n; j++, i++)
    big[i] = small[j];
  make_heap(small , small + left);
  make_heap(big , big + right, cmp);
//the numbers which is bigger than middle is stored in array big using small root heap
}

void insert(int *small, int *big, int &n, int &middle, int &left, int &right){
//insert a number into the data store
  int temp;
  cout<<"input a number to insert:";
  cin>>temp;
  n++;
  if(temp < middle){
  //the number which is smaller than middle is throwed into the array small
    small[left++] = temp;
    push_heap(small, small + left);
    //if the nodes of the two trees is biger than 2, change the root of the big root heap 
    if(left - right == 2){
    	big[right++] = middle;
    	push_heap(big, big + right, cmp);
    	pop_heap(small, small + left);
    	middle = small[--left];
    }
  }
  else{
    big[right++] = temp;
    push_heap(big ,big+ right, cmp);
    if(left - right ==  -2){
    	small[left++] = middle;
    	push_heap(small, small + left);
    	pop_heap(big,big + right, cmp);
    	middle = big[-- right];
    }
  }
//	test code****************
//  cout<<"small:";
//  show_array(small, left);
//  cout<<"middle:"<<middle<<endl;
//  cout<<"big:";
//  show_array(big, right);
}
int main(){
  int small[N];
  //store the big root heap
  int big[N];
  //the small root heap which stores the numbers bigger than middle; 
  int left;
  //the pointer of the big root heap
  int right;
  //the pointer of the small root heap
  int n;
  //the number of all numbers
  int middle;
  //the value of the median
  init(small, big, n, middle, left, right);
//  test code*******************
//  while(1)
//	  insert(small, big, n, middle, left, right);
}
